-
Online Control in Population Dynamics
Authors:
Noah Golowich,
Elad Hazan,
Zhou Lu,
Dhruv Rohatgi,
Y. Jennifer Sun
Abstract:
The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and economics. Most studies on population dynamics focus on the problem of prediction rather than control. Existing mathematical models for control in population dynamics are often restricted to specific, noise-free dynamics,…
▽ More
The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and economics. Most studies on population dynamics focus on the problem of prediction rather than control. Existing mathematical models for control in population dynamics are often restricted to specific, noise-free dynamics, while real-world population changes can be complex and adversarial.
To address this gap, we propose a new framework based on the paradigm of online control. We first characterize a set of linear dynamical systems that can naturally model evolving populations. We then give an efficient gradient-based controller for these systems, with near-optimal regret bounds with respect to a broad class of linear policies. Our empirical evaluations demonstrate the effectiveness of the proposed algorithm for control in population dynamics even for non-linear models such as SIR and replicator dynamics.
△ Less
Submitted 6 June, 2024; v1 submitted 3 June, 2024;
originally announced June 2024.
-
Single-loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
Authors:
Quanqi Hu,
Qi Qi,
Zhaosong Lu,
Tianbao Yang
Abstract:
In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in Y}φ(x, y) - \max_{z\in Z}ψ(x, z)]$, where both $Φ(x) = \max_{y\in Y}φ(x, y)$ and $Ψ(x)=\max_{z\in Z}ψ(x, z)$ are weakly convex functions, and $φ(x, y), ψ(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively. It covers two families of problems that have been studied but are m…
▽ More
In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in Y}φ(x, y) - \max_{z\in Z}ψ(x, z)]$, where both $Φ(x) = \max_{y\in Y}φ(x, y)$ and $Ψ(x)=\max_{z\in Z}ψ(x, z)$ are weakly convex functions, and $φ(x, y), ψ(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively. It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of $Φ, Ψ$ using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms.
△ Less
Submitted 29 May, 2024; v1 submitted 28 May, 2024;
originally announced May 2024.
-
Bistellar Cluster Algebras and Piecewise Linear Invariants
Authors:
Alastair Darby,
Fang Li,
Zhi Lu
Abstract:
Inspired by the ideas and techniques used in the study of cluster algebras we construct a new class of algebras, called bistellar cluster algebras, from closed oriented triangulated even-dimensional manifolds by performing middle-dimensional bistellar moves. This class of algebras exhibit the algebraic behaviour of middle-dimensional bistellar moves but do not satisfy the classical cluster algebra…
▽ More
Inspired by the ideas and techniques used in the study of cluster algebras we construct a new class of algebras, called bistellar cluster algebras, from closed oriented triangulated even-dimensional manifolds by performing middle-dimensional bistellar moves. This class of algebras exhibit the algebraic behaviour of middle-dimensional bistellar moves but do not satisfy the classical cluster algebra axiom: "every cluster variable in every cluster is exchangeable". Thus the construction of bistellar cluster algebras is quite different from that of a classical cluster algebra. Secondly, using bistellar cluster algebras and the techniques of combinatorial topology, we construct a direct system associated with a set of PL homeomorphic PL manifolds of dimension 2 or 4, and show that the limit of this direct system is a PL invariant.
△ Less
Submitted 15 May, 2024;
originally announced May 2024.
-
Angle-Aware Coverage with Camera Rotational Motion Control
Authors:
Zhiyuan Lu,
Muhammad Hanif,
Takumi Shimizu,
Takeshi Hatanaka
Abstract:
This paper presents a novel control strategy for drone networks to improve the quality of 3D structures reconstructed from aerial images by drones. Unlike the existing coverage control strategies for this purpose, our proposed approach simultaneously controls both the camera orientation and drone translational motion, enabling more comprehensive perspectives and enhancing the map's overall quality…
▽ More
This paper presents a novel control strategy for drone networks to improve the quality of 3D structures reconstructed from aerial images by drones. Unlike the existing coverage control strategies for this purpose, our proposed approach simultaneously controls both the camera orientation and drone translational motion, enabling more comprehensive perspectives and enhancing the map's overall quality. Subsequently, we present a novel problem formulation, including a new performance function to evaluate the drone positions and camera orientations. We then design a QP-based controller with a control barrier-like function for a constraint on the decay rate of the objective function. The present problem formulation poses a new challenge, requiring significantly greater computational efforts than the case involving only translational motion control. We approach this issue technologically, namely by introducing JAX, utilizing just-in-time (JIT) compilation and Graphical Processing Unit (GPU) acceleration. We finally conduct extensive verifications through simulation in ROS (Robot Operating System) and show the real-time feasibility of the controller and the superiority of the present controller to the conventional method.
△ Less
Submitted 22 April, 2024;
originally announced April 2024.
-
Differential Harnack inequalities for Fisher-KPP type equations on Riemannian manifolds
Authors:
Zhihao Lu
Abstract:
We obtain almost optimal differential Harnack inequalities for a class of nonlinear parabolic equations on Riemannian manifolds with Bakry-Émery Ricci curvature bounded below, which includes the classical Fisher-KPP equation and Newell-Whitehead equation. Compared to existing research, we do not impose any additional conditions on the positive solutions. As its application, we derive some optimal…
▽ More
We obtain almost optimal differential Harnack inequalities for a class of nonlinear parabolic equations on Riemannian manifolds with Bakry-Émery Ricci curvature bounded below, which includes the classical Fisher-KPP equation and Newell-Whitehead equation. Compared to existing research, we do not impose any additional conditions on the positive solutions. As its application, we derive some optimal Liouville properties.
△ Less
Submitted 10 April, 2024;
originally announced April 2024.
-
Integrated Optimal Control for Fast Charging and Active Thermal Management of Lithium-Ion Batteries in Extreme Ambient Temperatures
Authors:
Zehui Lu,
Hao Tu,
Huazhen Fang,
Yebin Wang,
Shaoshuai Mou
Abstract:
This paper presents an integrated control strategy for fast charging and active thermal management of Lithium-ion batteries in extreme ambient temperatures. A control-oriented thermal-NDC (nonlinear double-capacitor) battery model is proposed to describe the electrical and thermal dynamics, accounting for the impact from both an active thermal source and ambient temperature. A state-feedback model…
▽ More
This paper presents an integrated control strategy for fast charging and active thermal management of Lithium-ion batteries in extreme ambient temperatures. A control-oriented thermal-NDC (nonlinear double-capacitor) battery model is proposed to describe the electrical and thermal dynamics, accounting for the impact from both an active thermal source and ambient temperature. A state-feedback model predictive control algorithm is then developed for integrated fast charging and active thermal management. Numerical experiments validate the algorithm under extreme temperatures, showing that the proposed algorithm can energy-efficiently adjust the battery temperature to enhance fast charging. Additionally, an output-feedback model predictive control algorithm with an extended Kalman filter is proposed for battery charging when states are partially measurable. Numerical experiments validate the effectiveness under extreme temperatures.
△ Less
Submitted 5 April, 2024;
originally announced April 2024.
-
Measuring Multimodal Mathematical Reasoning with MATH-Vision Dataset
Authors:
Ke Wang,
Junting Pan,
Weikang Shi,
Zimu Lu,
Mingjie Zhan,
Hongsheng Li
Abstract:
Recent advancements in Large Multimodal Models (LMMs) have shown promising results in mathematical reasoning within visual contexts, with models approaching human-level performance on existing benchmarks such as MathVista. However, we observe significant limitations in the diversity of questions and breadth of subjects covered by these benchmarks. To address this issue, we present the MATH-Vision…
▽ More
Recent advancements in Large Multimodal Models (LMMs) have shown promising results in mathematical reasoning within visual contexts, with models approaching human-level performance on existing benchmarks such as MathVista. However, we observe significant limitations in the diversity of questions and breadth of subjects covered by these benchmarks. To address this issue, we present the MATH-Vision (MATH-V) dataset, a meticulously curated collection of 3,040 high-quality mathematical problems with visual contexts sourced from real math competitions. Spanning 16 distinct mathematical disciplines and graded across 5 levels of difficulty, our dataset provides a comprehensive and diverse set of challenges for evaluating the mathematical reasoning abilities of LMMs. Through extensive experimentation, we unveil a notable performance gap between current LMMs and human performance on MATH-V, underscoring the imperative for further advancements in LMMs. Moreover, our detailed categorization allows for a thorough error analysis of LMMs, offering valuable insights to guide future research and development. The project is available at https://mathvision-cuhk.github.io
△ Less
Submitted 22 February, 2024;
originally announced February 2024.
-
AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems
Authors:
Piyush Jha,
Zhengyu Li,
Zhengyang Lu,
Curtis Bright,
Vijay Ganesh
Abstract:
This paper introduces AlphaMapleSAT, a novel Monte Carlo Tree Search (MCTS) based Cube-and-Conquer (CnC) SAT solving method aimed at efficiently solving challenging combinatorial problems. Despite the tremendous success of CnC solvers in solving a variety of hard combinatorial problems, the lookahead cubing techniques at the heart of CnC have not evolved much for many years. Part of the reason is…
▽ More
This paper introduces AlphaMapleSAT, a novel Monte Carlo Tree Search (MCTS) based Cube-and-Conquer (CnC) SAT solving method aimed at efficiently solving challenging combinatorial problems. Despite the tremendous success of CnC solvers in solving a variety of hard combinatorial problems, the lookahead cubing techniques at the heart of CnC have not evolved much for many years. Part of the reason is the sheer difficulty of coming up with new cubing techniques that are both low-cost and effective in partitioning input formulas into sub-formulas, such that the overall runtime is minimized.
Lookahead cubing techniques used by current state-of-the-art CnC solvers, such as March, keep their cubing costs low by constraining the search for the optimal splitting variables. By contrast, our key innovation is a deductively-driven MCTS-based lookahead cubing technique, that performs a deeper heuristic search to find effective cubes, while keeping the cubing cost low. We perform an extensive comparison of AlphaMapleSAT against the March CnC solver on challenging combinatorial problems such as the minimum Kochen-Specker and Ramsey problems. We also perform ablation studies to verify the efficacy of the MCTS heuristic search for the cubing problem. Results show up to 2.3x speedup in parallel (and up to 27x in sequential) elapsed real time.
△ Less
Submitted 24 January, 2024;
originally announced January 2024.
-
$L^p$-spectral theory for the Laplacian on forms
Authors:
Nelia Charalambous,
Zhiqin Lu
Abstract:
In this article, we find sufficient conditions on an open Riemannian manifold so that a Weyl criterion holds for the $L^p$-spectrum of the Laplacian on $k$-forms, and also prove the decomposition of the $L^p$-spectrum depending on the order of the forms. We then show that the resolvent set of an operator such as the Laplacian on $L^p$ lies outside a parabola whenever the volume of the manifold has…
▽ More
In this article, we find sufficient conditions on an open Riemannian manifold so that a Weyl criterion holds for the $L^p$-spectrum of the Laplacian on $k$-forms, and also prove the decomposition of the $L^p$-spectrum depending on the order of the forms. We then show that the resolvent set of an operator such as the Laplacian on $L^p$ lies outside a parabola whenever the volume of the manifold has an exponential volume growth rate, removing the requirement on the manifold to be of bounded geometry. We conclude by providing a detailed description of the $L^p$ spectrum of the Laplacian on $k$-forms over hyperbolic space.
△ Less
Submitted 4 January, 2024;
originally announced January 2024.
-
Rigidity and quantitative stability for partially overdetermined problems and capillary CMC hypersurfaces
Authors:
Xiaohan Jia,
Zheng Lu,
Chao Xia,
Xuwen Zhang
Abstract:
In this paper, we first prove a rigidity result for a Serrin-type partially overdetermined problem in the half-space, which gives a characterization of capillary spherical caps by the overdetermined problem. In the second part, we prove quantitative stability results for the Serrin-type partially overdetermined problem, as well as capillary almost constant mean curvature hypersurfaces in the half-…
▽ More
In this paper, we first prove a rigidity result for a Serrin-type partially overdetermined problem in the half-space, which gives a characterization of capillary spherical caps by the overdetermined problem. In the second part, we prove quantitative stability results for the Serrin-type partially overdetermined problem, as well as capillary almost constant mean curvature hypersurfaces in the half-space.
△ Less
Submitted 30 November, 2023;
originally announced November 2023.
-
A characterization of capillary spherical caps by a partially overdetermined problem in a half ball
Authors:
Xiaohan Jia,
Zheng Lu,
Chao Xia,
Xuwen Zhang
Abstract:
In this note, we study a Serrin-type partially overdetermined problem proposed by Guo-Xia (Calc. Var. Partial Differential Equations 58: no. 160, 2019. https://doi.org/10.1007/s00526-019-1603-3, and prove a rigidity result that characterizes capillary spherical caps in a half ball.
In this note, we study a Serrin-type partially overdetermined problem proposed by Guo-Xia (Calc. Var. Partial Differential Equations 58: no. 160, 2019. https://doi.org/10.1007/s00526-019-1603-3, and prove a rigidity result that characterizes capillary spherical caps in a half ball.
△ Less
Submitted 30 November, 2023;
originally announced November 2023.
-
Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian
Authors:
Chuan He,
Zhaosong Lu
Abstract:
In this paper we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Hölder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate first-order stationary point (FOSP) of this problem, assuming the associated the Hölder parameters are explicitly known. Then we develop…
▽ More
In this paper we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Hölder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate first-order stationary point (FOSP) of this problem, assuming the associated the Hölder parameters are explicitly known. Then we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To the best of our knowledge, this method is the first parameter-free second-order method achieving the best-known iteration and operation complexity for finding an approximate FOSP of this problem. Furthermore, we propose a Newton-CG method for finding an approximate second-order stationary point (SOSP) of the considered problem with high probability and establish its iteration and operation complexity. Finally, we present preliminary numerical results to demonstrate the superior practical performance of our parameter-free Newton-CG method over a well-known regularized Newton method.
△ Less
Submitted 21 November, 2023;
originally announced November 2023.
-
Remarks on a result of Chen-Cheng
Authors:
Zhiqin Lu,
Reza Seyyedali
Abstract:
In their seminal work (\cite{CC}, \cite{CC2}), Chen and Cheng proved apriori estimates for the constant scalar curvature metrics on compact Kähler manifolds. They also prove $C^{3,α}$-estimate for the potential of the Kähler metrics under boundedness assumption on the scalar curvature and the entropy. The goal of this paper is to replace the uniform boundedness of the scalar curvature to the…
▽ More
In their seminal work (\cite{CC}, \cite{CC2}), Chen and Cheng proved apriori estimates for the constant scalar curvature metrics on compact Kähler manifolds. They also prove $C^{3,α}$-estimate for the potential of the Kähler metrics under boundedness assumption on the scalar curvature and the entropy. The goal of this paper is to replace the uniform boundedness of the scalar curvature to the $L^p$-boundedness of the scalar curvature.
△ Less
Submitted 1 November, 2023;
originally announced November 2023.
-
Solving Inverse Problems with Reinforcement Learning
Authors:
Chen Xu,
Zhipeng Lu,
Ye Zhang
Abstract:
In this paper, we formally introduce, with rigorous derivations, the use of reinforcement learning to the field of inverse problems by designing an iterative algorithm, called REINFORCE-IP, for solving a general type of non-linear inverse problem. By choosing specific probability models for the action-selection rule, we connect our approach to the conventional regularization methods of Tikhonov re…
▽ More
In this paper, we formally introduce, with rigorous derivations, the use of reinforcement learning to the field of inverse problems by designing an iterative algorithm, called REINFORCE-IP, for solving a general type of non-linear inverse problem. By choosing specific probability models for the action-selection rule, we connect our approach to the conventional regularization methods of Tikhonov regularization and iterative regularization. For the numerical implementation of our approach, we parameterize the solution-searching rule with the help of neural networks and iteratively improve the parameter using a reinforcement-learning algorithm~-- REINFORCE. Under standard assumptions we prove the almost sure convergence of the parameter to a locally optimal value. Our work provides two typical examples (non-linear integral equations and parameter-identification problems in partial differential equations) of how reinforcement learning can be applied in solving non-linear inverse problems. Our numerical experiments show that REINFORCE-IP is an efficient algorithm that can escape from local minimums and identify multi-solutions for inverse problems with non-uniqueness.
△ Less
Submitted 13 November, 2023; v1 submitted 10 October, 2023;
originally announced October 2023.
-
Representation theorems for functions of vanishing mean oscillation
Authors:
Zheng-yi Lu,
Fei Tao,
Yaosong Yang
Abstract:
As a significant application of the duality theory between real Hardy spaces $H^1(\mathbb{R}^n)$ and $\mathrm{BMO}(\mathbb{R}^n)$, Fefferman and Stein developed a representation theorem for $\mathrm{BMO}(\mathbb{R}^n)$ by utilizing the Riesz transforms $(n\geq 1)$. L. Carleson provided a constructive proof for the case $n=1$. In this article, we propose a representation theorem for…
▽ More
As a significant application of the duality theory between real Hardy spaces $H^1(\mathbb{R}^n)$ and $\mathrm{BMO}(\mathbb{R}^n)$, Fefferman and Stein developed a representation theorem for $\mathrm{BMO}(\mathbb{R}^n)$ by utilizing the Riesz transforms $(n\geq 1)$. L. Carleson provided a constructive proof for the case $n=1$. In this article, we propose a representation theorem for $\mathrm{VMO}(\mathbb{S})$ using Carleson's construction and demonstrate a representation theorem for $\mathrm{VMO}(\mathbb{R}^n)$ through an iterative process. Additionally, we provide a brand-new characterization of $\mathrm{VMO}$ as an application of our results.
△ Less
Submitted 12 September, 2023;
originally announced September 2023.
-
Risk-aware Flexible Resource Utilization in an Unbalanced Three-Phase Distribution Network using SDP-based Distributionally Robust Optimal Power Flow
Authors:
Zelong Lu,
Jianxue Wang,
Mohammad Shahidehpour,
Linquan Bai,
Zuyi Li,
Lei Yan,
Xianlong Chen
Abstract:
The variability caused by the proliferation of distributed energy resources (DERs) and the significant growth in unbalanced three-phase loads pose unprecedented challenges to distribution network operations. This paper focuses on how a distribution system operator (DSO), taking over the distribution grid and market operations, would develop a risk-aware flexibility market to mitigate uncertainties…
▽ More
The variability caused by the proliferation of distributed energy resources (DERs) and the significant growth in unbalanced three-phase loads pose unprecedented challenges to distribution network operations. This paper focuses on how a distribution system operator (DSO), taking over the distribution grid and market operations, would develop a risk-aware flexibility market to mitigate uncertainties in an unbalanced three-phase power distribution network. First, a distributionally robust chance constraint (DRCC) method is devised to solve the unbalanced three-phase optimal power flow using a semidefinite programming (SDP) model. The DSO can apply the proposed solution to jointly clear energy and flexibility markets. Then, the DRCC model accuracy is improved by an information-sharing mechanism characterized by spatially-correlated uncertainties in the distribution grid. Further, a novel system-wide response function is derived to make the DRCC model tractable. Using the duality theory, the paper further investigates the physical composition of the DSO's cleared flexibility prices to guide the unbalanced distribution network operation. Finally, the effectiveness of the risk-aware flexibility market is verified in a modified three-phase IEEE 34-node system. Results demonstrate that the flexibility market can quantify the impact of spatially correlated uncertainties and facilitate the utilization of flexible resources to mitigate uncertainties across the network.
△ Less
Submitted 29 August, 2023;
originally announced August 2023.
-
Gradient estimate and Universal bounds for semilinear elliptic equations on RCD$^*$(K,N) metric measure spaces
Authors:
Zhihao Lu
Abstract:
We provide logarithmic gradient estimate and universal boundedness estimate for semilinear elliptic equations on RCD$^*(K,N)$, metric measure spaces. In certain case, these estimates are optimal even on RCD$^*(K,N)$ spaces with $K<0$. Two direct corollaries of these estimates are Harnack inequality and Liouville theorem. In addition to these estimates, we also establish relations among the univers…
▽ More
We provide logarithmic gradient estimate and universal boundedness estimate for semilinear elliptic equations on RCD$^*(K,N)$, metric measure spaces. In certain case, these estimates are optimal even on RCD$^*(K,N)$ spaces with $K<0$. Two direct corollaries of these estimates are Harnack inequality and Liouville theorem. In addition to these estimates, we also establish relations among the universal boundedness estimate, the logarithmic gradient estimate, and Harnack inequality. Under certain conditions, even in wild setting, they are $κ$-equivalent on RCD$^*(0,N)$ spaces for any $κ>1$.
△ Less
Submitted 27 August, 2023;
originally announced August 2023.
-
Logarithmic gradient estimate and Universal bounds for semilinear elliptic equations revisited
Authors:
Zhihao Lu
Abstract:
We use the Bernstein method to provide logarithmic gradient estimates and universal boundedness estimates for semilinear elliptic equations that satisfy the subcritical index condition. Our estimates are applicable to equations on Riemannian manifolds with (Bakry-Émery) Ricci curvature that is bounded below, and they are original for many concrete equations, even on Euclidean spaces that have been…
▽ More
We use the Bernstein method to provide logarithmic gradient estimates and universal boundedness estimates for semilinear elliptic equations that satisfy the subcritical index condition. Our estimates are applicable to equations on Riemannian manifolds with (Bakry-Émery) Ricci curvature that is bounded below, and they are original for many concrete equations, even on Euclidean spaces that have been carefully investigated by numerous experts. Under the (Bakry-Émery) Ricci curvature bounded below condition, we establish relations among basic estimates, such as the universal boundedness estimate, logarithmic gradient estimate, and Harnack inequality. Under the (Bakry-Émery) Ricci curvature non-negative condition and certain mild assumptions, these estimates are $κ$-equivalent for any $κ>1$. As an application, we obtain optimal pointwise estimates and Liouville theorems for specific equations on Euclidean spaces.
△ Less
Submitted 27 August, 2023;
originally announced August 2023.
-
Liouville theorems and Harnack inequalities for Allen-Cahn type equation
Authors:
Zhihao Lu
Abstract:
We first give a logarithmic gradient estimate for positive solutions of Allen-Cahn equation on Riemannian manifolds with Ricci curvature bounded below. As its natural corallary, Harnack inequality and a Liouville theorem for classical positive solutions are obtained. Later, we consider similar estimate under integral curvature condition and generalize previous results to a class nonlinear equation…
▽ More
We first give a logarithmic gradient estimate for positive solutions of Allen-Cahn equation on Riemannian manifolds with Ricci curvature bounded below. As its natural corallary, Harnack inequality and a Liouville theorem for classical positive solutions are obtained. Later, we consider similar estimate under integral curvature condition and generalize previous results to a class nonlinear equations which contain some classical elliptic equations such as Lane-Emden equation, static Whitehead-Newell equation and static Fisher-KPP equation. Last, we briefly generalize them to equation with gradient item under Bakry-Émery curvature condition.
△ Less
Submitted 10 April, 2024; v1 submitted 21 August, 2023;
originally announced August 2023.
-
Differential Harnack inequalities for semilinear parabolic equations on Riemannian manifolds I: Bakry-Émery curvature bounded below
Authors:
Zhihao Lu
Abstract:
In this paper, we present a unified method for deriving differential Harnack inequalities for positive solutions of the semilinear parabolic equation \begin{equation*}
\partial_t u=Δ_V u+H(u) \end{equation*} on complete Riemannian manifolds with Bakry-Émery curvature bounded below. This method transforms the problem of deriving differential Harnack inequalities into solving a related ODE system.…
▽ More
In this paper, we present a unified method for deriving differential Harnack inequalities for positive solutions of the semilinear parabolic equation \begin{equation*}
\partial_t u=Δ_V u+H(u) \end{equation*} on complete Riemannian manifolds with Bakry-Émery curvature bounded below. This method transforms the problem of deriving differential Harnack inequalities into solving a related ODE system. As an application of this method, we obtain new and improved estimates for logarithmic-type equations and Yamabe-type equations. Moreover, under the non-negative Bakry-Émery curvature condition, we obtain complete sharp estimates for these equations. As a natural consequence of these results, we also establish sharp Harnack inequalities and Liouville-type theorems for these equations.
△ Less
Submitted 18 August, 2023;
originally announced August 2023.
-
On symmetric 2-designs of prime order with almost simple flag-transitive automorphism groups
Authors:
Z. W. Lu,
S. L. Zhou
Abstract:
In this article, we investigate symmetric 2-designs of prime order admitting a flag-transitive automorphism group G. Recently, the authors proved that the automorphism group G of this type of designs must be point-primitive, and is of affine or almost simple type. Here, we give the complete classification of symmetric 2-designs of prime order, admitting a flag-transitive almost simple automorphism…
▽ More
In this article, we investigate symmetric 2-designs of prime order admitting a flag-transitive automorphism group G. Recently, the authors proved that the automorphism group G of this type of designs must be point-primitive, and is of affine or almost simple type. Here, we give the complete classification of symmetric 2-designs of prime order, admitting a flag-transitive almost simple automorphism group.
△ Less
Submitted 25 July, 2023;
originally announced July 2023.
-
Iterated residue, toric forms and Witten genus
Authors:
Fei Han,
Hao Li,
Zhi Lü
Abstract:
We introduce the notion of {\em iterated residue} to study generalized Bott manifolds. When applying the iterated residues to compute the Borisov-Gunnells toric form and the Witten genus of certain toric varieties as well as complete intersections, we obtain interesting vanishing results and some theta function identities, one of which is a twisted version of a classical Rogers-Ramanujan type form…
▽ More
We introduce the notion of {\em iterated residue} to study generalized Bott manifolds. When applying the iterated residues to compute the Borisov-Gunnells toric form and the Witten genus of certain toric varieties as well as complete intersections, we obtain interesting vanishing results and some theta function identities, one of which is a twisted version of a classical Rogers-Ramanujan type formula.
△ Less
Submitted 22 June, 2023;
originally announced June 2023.
-
A Parameter-Free Conditional Gradient Method for Composite Minimization under Hölder Condition
Authors:
Masaru Ito,
Zhaosong Lu,
Chuan He
Abstract:
In this paper we consider a composite optimization problem that minimizes the sum of a weakly smooth function and a convex function with either a bounded domain or a uniformly convex structure. In particular, we first present a parameter-dependent conditional gradient method for this problem, whose step sizes require prior knowledge of the parameters associated with the Hölder continuity of the gr…
▽ More
In this paper we consider a composite optimization problem that minimizes the sum of a weakly smooth function and a convex function with either a bounded domain or a uniformly convex structure. In particular, we first present a parameter-dependent conditional gradient method for this problem, whose step sizes require prior knowledge of the parameters associated with the Hölder continuity of the gradient of the weakly smooth function, and establish its rate of convergence. Given that these parameters could be unknown or known but possibly conservative, such a method may suffer from implementation issue or slow convergence. We therefore propose a parameter-free conditional gradient method whose step size is determined by using a constructive local quadratic upper approximation and an adaptive line search scheme, without using any problem parameter. We show that this method achieves the same rate of convergence as the parameter-dependent conditional gradient method. Preliminary experiments are also conducted and illustrate the superior performance of the parameter-free conditional gradient method over the methods with some other step size rules.
△ Less
Submitted 29 May, 2023;
originally announced May 2023.
-
Distributed Optimization under Edge Agreements: A Continuous-Time Algorithm
Authors:
Zehui Lu,
Shaoshuai Mou
Abstract:
Generalized from the concept of consensus, this paper considers a group of edge agreements, i.e. constraints defined for neighboring agents, in which each pair of neighboring agents is required to satisfy one edge agreement constraint. Edge agreements are defined locally to allow more flexibility than a global consensus. This work formulates a multi-agent optimization problem under edge agreements…
▽ More
Generalized from the concept of consensus, this paper considers a group of edge agreements, i.e. constraints defined for neighboring agents, in which each pair of neighboring agents is required to satisfy one edge agreement constraint. Edge agreements are defined locally to allow more flexibility than a global consensus. This work formulates a multi-agent optimization problem under edge agreements and proposes a continuous-time distributed algorithm to solve it. Both analytical proof and numerical examples are provided to validate the effectiveness of the proposed algorithm.
△ Less
Submitted 30 November, 2023; v1 submitted 26 May, 2023;
originally announced May 2023.
-
The spectrality of Cantor-Moran measure and Fuglede's Conjecture
Authors:
Jinsong Liu,
Zheng-yi Lu,
Ting Zhou
Abstract:
Let $\{(p_n, \mathcal{D}_n, L_n)\}$ be a sequence of Hadamard triples on $\mathbb{R}$. Suppose that the associated Cantor-Moran measure $$ μ_{\{p_n,\mathcal{D}_n\}}=δ_{p_1^{-1}\mathcal{D}_1}\astδ_{(p_2p_1)^{-1}\mathcal{D}_2}\ast\cdots, $$ where $\sup_n\{|p_n^{-1}d|:d\in \mathcal{D}_n\}<\infty$ and $\sup\#\mathcal{D}_n<\infty$. It has been observed that the spectrality of $μ_{\{p_n,D_n\}}$ is deter…
▽ More
Let $\{(p_n, \mathcal{D}_n, L_n)\}$ be a sequence of Hadamard triples on $\mathbb{R}$. Suppose that the associated Cantor-Moran measure $$ μ_{\{p_n,\mathcal{D}_n\}}=δ_{p_1^{-1}\mathcal{D}_1}\astδ_{(p_2p_1)^{-1}\mathcal{D}_2}\ast\cdots, $$ where $\sup_n\{|p_n^{-1}d|:d\in \mathcal{D}_n\}<\infty$ and $\sup\#\mathcal{D}_n<\infty$. It has been observed that the spectrality of $μ_{\{p_n,D_n\}}$ is determined by equi-positivity. A significant problem is what kind of Moran measures can satisfy this property. In this paper, we introduce the conception of \textit{Double Points Condition Set} (\textit{DPCS}) to characterize the equi-positivity equivalently. As applications of our characterization, we show that all singularly continuous Cantor-Moran measures are spectral. For the absolutely continuous case, we study Fuglede's Conjecture on Cantor-Moran set. We show that the equi-positivity of $μ_{\{p_n,D_n\}}$ implies the tiling of its support, and the reverse direction holds under certain conditions.
△ Less
Submitted 21 June, 2023; v1 submitted 20 May, 2023;
originally announced May 2023.
-
Capillary Schwarz symmetrization in the half-space
Authors:
Zheng Lu,
Chao Xia,
Xuwen Zhang
Abstract:
In this paper, we introduce a notion of capillary Schwarz symmetrization in the half-space. It can be viewed as the counterpart of the classical Schwarz symmetrization in the framework of capillary problem in the half-space. A key ingredient is a special anisotropic gauge, which enables us to transform the capillary symmetrization to the convex symmetrization introduced in \cite{AFT97}.
In this paper, we introduce a notion of capillary Schwarz symmetrization in the half-space. It can be viewed as the counterpart of the classical Schwarz symmetrization in the framework of capillary problem in the half-space. A key ingredient is a special anisotropic gauge, which enables us to transform the capillary symmetrization to the convex symmetrization introduced in \cite{AFT97}.
△ Less
Submitted 4 April, 2023;
originally announced April 2023.
-
Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
Authors:
Ziyi Chen,
Yi Zhou,
Yingbin Liang,
Zhaosong Lu
Abstract:
Various optimal gradient-based algorithms have been developed for smooth nonconvex optimization. However, many nonconvex machine learning problems do not belong to the class of smooth functions and therefore the existing algorithms are sub-optimal. Instead, these problems have been shown to satisfy certain generalized-smooth conditions, which have not been well understood in the existing literatur…
▽ More
Various optimal gradient-based algorithms have been developed for smooth nonconvex optimization. However, many nonconvex machine learning problems do not belong to the class of smooth functions and therefore the existing algorithms are sub-optimal. Instead, these problems have been shown to satisfy certain generalized-smooth conditions, which have not been well understood in the existing literature. In this paper, we propose a notion of $α$-symmetric generalized-smoothness that extends the existing notions and covers many important functions such as high-order polynomials and exponential functions. We study the fundamental properties and establish descent lemmas for the functions in this class. Then, to solve such a large class of nonconvex problems, we design a special deterministic normalized gradient descent algorithm that achieves the optimal iteration complexity $\mathcal{O}(ε^{-2})$, and also prove that the popular SPIDER variance reduction algorithm achieves the optimal sample complexity $\mathcal{O}(ε^{-3})$ in the stochastic setting. Our results show that solving generalized-smooth nonconvex problems is as efficient as solving smooth nonconvex problems.
△ Less
Submitted 24 June, 2023; v1 submitted 5 March, 2023;
originally announced March 2023.
-
Variable Sampling MPC via Differentiable Time-Warping Function
Authors:
Zehui Lu,
Shaoshuai Mou
Abstract:
Designing control inputs for a system that involves dynamical responses in multiple timescales is nontrivial. This paper proposes a parameterized time-warping function to enable a non-uniformly sampling along a prediction horizon given some parameters. The horizon should capture the responses under faster dynamics in the near future and preview the impact from slower dynamics in the distant future…
▽ More
Designing control inputs for a system that involves dynamical responses in multiple timescales is nontrivial. This paper proposes a parameterized time-warping function to enable a non-uniformly sampling along a prediction horizon given some parameters. The horizon should capture the responses under faster dynamics in the near future and preview the impact from slower dynamics in the distant future. Then a variable sampling MPC (VS-MPC) strategy is proposed to jointly determine optimal control and sampling parameters at each timestamp. VS-MPC adapts how it samples along the horizon and determines optimal control accordingly at each timestamp without offline tuning or trial and error. A numerical example of a wind farm battery energy storage system is also provided to demonstrate that VS-MPC outperforms the uniform sampling MPC.
△ Less
Submitted 20 March, 2023; v1 submitted 19 January, 2023;
originally announced January 2023.
-
Four limit cycles in three-dimensional Lotka-Volterra competitive systems with classes 28, 30 and 31 in Zeemans classification via automatic search
Authors:
Mingzhi Hu,
Zhengyi Lu,
Yong Luo
Abstract:
Four limit cycles are constructed for classes 28, 30 and 31 in Zeeman's classification, together with the results in [5 ] for class 27, [20] for class 29 and [22] for class 26 which indicate that for each class among classes 26-31, there exist at least four limit cycles. This gives a partial answer to a problem proposed in [22] as well as in [7].
Four limit cycles are constructed for classes 28, 30 and 31 in Zeeman's classification, together with the results in [5 ] for class 27, [20] for class 29 and [22] for class 26 which indicate that for each class among classes 26-31, there exist at least four limit cycles. This gives a partial answer to a problem proposed in [22] as well as in [7].
△ Less
Submitted 14 March, 2023; v1 submitted 17 January, 2023;
originally announced January 2023.
-
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
Authors:
Chuan He,
Heng Huang,
Zhaosong Lu
Abstract:
In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this p…
▽ More
In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under some mild assumptions, we show that our method enjoys a total inner iteration complexity of $\widetilde{\cal O}(ε^{-11/2})$ and an operation complexity of $\widetilde{\cal O}(ε^{-11/2}\min\{n,ε^{-5/4}\})$ for finding an $(ε,\sqrtε)$-SOSP of general nonconvex conic optimization with high probability. Moreover, under a constraint qualification, these complexity bounds are improved to $\widetilde{\cal O}(ε^{-7/2})$ and $\widetilde{\cal O}(ε^{-7/2}\min\{n,ε^{-3/4}\})$, respectively. To the best of our knowledge, this is the first study on the complexity of finding an approximate SOSP of general nonconvex conic optimization. Preliminary numerical results are presented to demonstrate superiority of the proposed method over first-order methods in terms of solution quality.
△ Less
Submitted 10 January, 2023;
originally announced January 2023.
-
A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees
Authors:
Chuan He,
Zhaosong Lu,
Ting Kei Pong
Abstract:
In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We then propose a Newton-CG based…
▽ More
In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of $\widetilde{\cal O}(ε^{-7/2})$ and an operation complexity of $\widetilde{\cal O}(ε^{-7/2}\min\{n,ε^{-3/4}\})$ for finding an $(ε,\sqrtε)$-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method [60]. Besides, we show that it has a total inner iteration complexity of $\widetilde{\cal O}(ε^{-11/2})$ and an operation complexity of $\widetilde{\cal O}(ε^{-11/2}\min\{n,ε^{-5/4}\})$ when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the ones in [56,60].
△ Less
Submitted 8 January, 2023;
originally announced January 2023.
-
A first-order augmented Lagrangian method for constrained minimax optimization
Authors:
Zhaosong Lu,
Sanyou Mei
Abstract:
In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, an \emph{operation complexity} of…
▽ More
In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, an \emph{operation complexity} of ${\cal O}(\varepsilon^{-4}\log\varepsilon^{-1})$, measured by its fundamental operations, is established for the first-order augmented Lagrangian method for finding an $\varepsilon$-KKT solution of the constrained minimax problems.
△ Less
Submitted 17 April, 2023; v1 submitted 5 January, 2023;
originally announced January 2023.
-
First-order penalty methods for bilevel optimization
Authors:
Zhaosong Lu,
Sanyou Mei
Abstract:
In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower level is a possibly nonsmooth convex optimization problem, while the upper level is a possibly nonconvex optimization problem. We introduce a notion of $\varepsilon$-KKT solution for them and show that an $\varepsilon$-KKT solution leads to an $O(\sqrt{\varepsilon})$- or…
▽ More
In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower level is a possibly nonsmooth convex optimization problem, while the upper level is a possibly nonconvex optimization problem. We introduce a notion of $\varepsilon$-KKT solution for them and show that an $\varepsilon$-KKT solution leads to an $O(\sqrt{\varepsilon})$- or $O(\varepsilon)$-hypergradient based stionary point under suitable assumptions. We also propose first-order penalty methods for finding an $\varepsilon$-KKT solution of them, whose subproblems turn out to be a structured minimax problem and can be suitably solved by a first-order method recently developed by the authors. Under suitable assumptions, an \emph{operation complexity} of $O(\varepsilon^{-4}\log\varepsilon^{-1})$ and $O(\varepsilon^{-7}\log\varepsilon^{-1})$, measured by their fundamental operations, is established for the proposed penalty methods for finding an $\varepsilon$-KKT solution of the unconstrained and constrained bilevel optimization problems, respectively. Preliminary numerical results are presented to illustrate the performance of our proposed methods. To the best of our knowledge, this paper is the first work to demonstrate that bilevel optimization can be approximately solved as minimax optimization, and moreover, it provides the first implementable method with complexity guarantees for such sophisticated bilevel optimization.
△ Less
Submitted 7 March, 2024; v1 submitted 4 January, 2023;
originally announced January 2023.
-
A homogeneous method in summation with log factors and its application
Authors:
Zhipeng Lu
Abstract:
We introduce a homogeneous method to deal with summations with homogeneous factors. Then we use it to compute main terms in the asymptotics of distance energy of square lattices in circles, which relates to the conjecture of distinct distances by Erdos.
We introduce a homogeneous method to deal with summations with homogeneous factors. Then we use it to compute main terms in the asymptotics of distance energy of square lattices in circles, which relates to the conjecture of distinct distances by Erdos.
△ Less
Submitted 29 November, 2022;
originally announced November 2022.
-
Asymptotic estimate on the distance energy of lattices
Authors:
Zhipeng Lu,
Xianchang Meng
Abstract:
Since the well-known breakthrough of L. Guth and N. Katz on the Erdos distinct distances problem in the plane, mainstream of interest is aroused by their method and the Elekes-Sharir framework. In short words, they study the second moment in the framework. One may wonder if higher moments would be more efficient. In this paper, we show that any higher moment fails the expectation. In addition, we…
▽ More
Since the well-known breakthrough of L. Guth and N. Katz on the Erdos distinct distances problem in the plane, mainstream of interest is aroused by their method and the Elekes-Sharir framework. In short words, they study the second moment in the framework. One may wonder if higher moments would be more efficient. In this paper, we show that any higher moment fails the expectation. In addition, we show that the second moment gives optimal estimate in higher dimensions.
△ Less
Submitted 22 November, 2022;
originally announced November 2022.
-
Projection-free Adaptive Regret with Membership Oracles
Authors:
Zhou Lu,
Nataly Brukhim,
Paula Gradu,
Elad Hazan
Abstract:
In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle this problem HK12 proposed the study of projection-free methods that replace projections with less expensive computations. The most common approach is based on the Frank-Wolfe method, that uses linear optimization compu…
▽ More
In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle this problem HK12 proposed the study of projection-free methods that replace projections with less expensive computations. The most common approach is based on the Frank-Wolfe method, that uses linear optimization computation in lieu of projections. Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach.
In this work we give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations. We propose a simple lazy gradient-based algorithm with a Minkowski regularization that attains near-optimal adaptive regret bounds. For general convex loss functions we improve previous adaptive regret bounds from $O(T^{3/4})$ to $O(\sqrt{T})$, and further to tight interval dependent bound $\tilde{O}(\sqrt{I})$ where $I$ denotes the interval length. For strongly convex functions we obtain the first poly-logarithmic adaptive regret bounds using a projection-free algorithm.
△ Less
Submitted 14 December, 2022; v1 submitted 22 November, 2022;
originally announced November 2022.
-
On 2-arc-transitive graphs of product action type
Authors:
Zai Ping Lu
Abstract:
In this paper, we discuss the structural information about 2-arc-transitive (non-bipartite and bipartite) graphs of product action type. It is proved that a 2-arc-transitive graph of product action type requires certain restrictions on either the vertex-stabilizers or the valency. Based on the existence of some equidistant linear codes, a construction is given for 2-arc-transitive graphs of non-di…
▽ More
In this paper, we discuss the structural information about 2-arc-transitive (non-bipartite and bipartite) graphs of product action type. It is proved that a 2-arc-transitive graph of product action type requires certain restrictions on either the vertex-stabilizers or the valency. Based on the existence of some equidistant linear codes, a construction is given for 2-arc-transitive graphs of non-diagonal product action type, which produces several families of such graphs. Besides, a nontrivial construction is given for 2-arc-transitive bipartite graphs of diagonal product action type
△ Less
Submitted 9 November, 2022;
originally announced November 2022.
-
A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees
Authors:
Chuan He,
Zhaosong Lu
Abstract:
In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an $(ε,\sqrtε)$-SOSP of this problem. Our method is not only implementabl…
▽ More
In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an $(ε,\sqrtε)$-SOSP of this problem. Our method is not only implementable, but also achieves an iteration complexity of ${\cal O}(ε^{-3/2})$, which matches the best known iteration complexity of second-order methods for finding an $(ε,\sqrtε)$-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of ${\cal O}(ε^{-3/2})$ Cholesky factorizations and $\widetilde{\cal O}(ε^{-3/2}\min\{n,ε^{-1/4}\})$ other fundamental operations, is also established for our method.
△ Less
Submitted 11 October, 2022; v1 submitted 12 July, 2022;
originally announced July 2022.
-
Optimal Parallel Sequential Change Detection under Generalized Performance Measures
Authors:
Zexian Lu,
Yunxiao Chen,
Xiaoou Li
Abstract:
This paper considers the detection of change points in parallel data streams, a problem widely encountered when analyzing large-scale real-time streaming data. Each stream may have its own change point, at which its data has a distributional change. With sequentially observed data, a decision maker needs to declare whether changes have already occurred to the streams at each time point.Once a stre…
▽ More
This paper considers the detection of change points in parallel data streams, a problem widely encountered when analyzing large-scale real-time streaming data. Each stream may have its own change point, at which its data has a distributional change. With sequentially observed data, a decision maker needs to declare whether changes have already occurred to the streams at each time point.Once a stream is declared to have changed, it is deactivated permanently so that its future data will no longer be collected. This is a compound decision problem in the sense that the decision maker may want to optimize certain compound performance metrics that concern all the streams as a whole. Thus, the decisions are not independent for different streams. Our contribution is three-fold. First, we propose a general framework for compound performance metrics that includes the ones considered in the existing works as special cases and introduces new ones that connect closely with the performance metrics for single-stream sequential change detection and large-scale hypothesis testing. Second, data-driven decision procedures are developed under this framework. Finally, optimality results are established for the proposed decision procedures. The proposed methods and theory are evaluated by simulation studies and a case study.
△ Less
Submitted 16 June, 2022;
originally announced June 2022.
-
Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient
Authors:
Zhaosong Lu,
Sanyou Mei
Abstract:
In this paper we develop accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient (LLCG), which is beyond the well-studied class of convex optimization with Lipschitz continuous gradient. In particular, we first consider unconstrained convex optimization with LLCG and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG meth…
▽ More
In this paper we develop accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient (LLCG), which is beyond the well-studied class of convex optimization with Lipschitz continuous gradient. In particular, we first consider unconstrained convex optimization with LLCG and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG methods are equipped with a verifiable termination criterion and enjoy an operation complexity of ${\cal O}(\varepsilon^{-1/2}\log \varepsilon^{-1})$ and ${\cal O}(\log \varepsilon^{-1})$ for finding an $\varepsilon$-residual solution of an unconstrained convex and strongly convex optimization problem, respectively. We then consider constrained convex optimization with LLCG and propose an first-order proximal augmented Lagrangian method for solving it by applying one of our proposed APG methods to approximately solve a sequence of proximal augmented Lagrangian subproblems. The resulting method is equipped with a verifiable termination criterion and enjoys an operation complexity of ${\cal O}(\varepsilon^{-1}\log \varepsilon^{-1})$ and ${\cal O}(\varepsilon^{-1/2}\log \varepsilon^{-1})$ for finding an $\varepsilon$-KKT solution of a constrained convex and strongly convex optimization problem, respectively. All the proposed methods in this paper are parameter-free or almost parameter-free except that the knowledge on convexity parameter is required. In addition, preliminary numerical results are presented to demonstrate the performance of our proposed methods. To the best of our knowledge, no prior studies were conducted to investigate accelerated first-order methods with complexity guarantees for convex optimization with LLCG. All the complexity results obtained in this paper are new.
△ Less
Submitted 10 April, 2023; v1 submitted 2 June, 2022;
originally announced June 2022.
-
Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity with applications to variational inequality, conic constrained saddle point, and convex conic optimization problems
Authors:
Zhaosong Lu,
Sanyou Mei
Abstract:
In this paper we consider a class of structured monotone inclusion (MI) problems that consist of finding a zero in the sum of two monotone operators, in which one is maximal monotone while another is locally Lipschitz continuous. In particular, we first propose a primal-dual extrapolation (PDE) method for solving a structured strongly MI problem by modifying the classical forward-backward splittin…
▽ More
In this paper we consider a class of structured monotone inclusion (MI) problems that consist of finding a zero in the sum of two monotone operators, in which one is maximal monotone while another is locally Lipschitz continuous. In particular, we first propose a primal-dual extrapolation (PDE) method for solving a structured strongly MI problem by modifying the classical forward-backward splitting method by using a point and operator extrapolation technique, in which the parameters are adaptively updated by a backtracking line search scheme. The proposed PDE method is almost parameter-free, equipped with a verifiable termination criterion, and enjoys an operation complexity of ${\cal O}(\log ε^{-1})$, measured by the amount of fundamental operations consisting only of evaluations of one operator and resolvent of another operator, for finding an $ε$-residual solution of the structured strongly MI problem. We then propose another PDE method for solving a structured non-strongly MI problem by applying the above PDE method to approximately solve a sequence of structured strongly MI problems. The resulting PDE method is parameter-free, equipped with a verifiable termination criterion, and enjoys an operation complexity of ${\cal O}(ε^{-1}\log ε^{-1})$ for finding an $ε$-residual solution of the structured non-strongly MI problem. As a consequence, we apply the latter PDE method to convex conic optimization, conic constrained saddle point, and variational inequality problems, and obtain complexity results for finding an $ε$-KKT or $ε$-residual solution of them under local Lipschitz continuity. To the best of our knowledge, no prior studies were conducted to investigate methods with complexity guarantees for solving the aforementioned problems under local Lipschitz continuity. All the complexity results obtained in this paper are entirely new.
△ Less
Submitted 24 June, 2022; v1 submitted 2 June, 2022;
originally announced June 2022.
-
A note on Cheeger's isoperimetric constant
Authors:
Nelia Charalambous,
Zhiqin Lu
Abstract:
In this short exposition we provide a simplified proof of Buser's result for Cheeger's isoperimetric constant.
In this short exposition we provide a simplified proof of Buser's result for Cheeger's isoperimetric constant.
△ Less
Submitted 28 December, 2022; v1 submitted 1 June, 2022;
originally announced June 2022.
-
Non-convex online learning via algorithmic equivalence
Authors:
Udaya Ghai,
Zhou Lu,
Elad Hazan
Abstract:
We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking at a harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to non-convex functions is an approximation of online mirror descent applied to convex functions…
▽ More
We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking at a harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to non-convex functions is an approximation of online mirror descent applied to convex functions under reparameterization. In continuous time, the gradient flow with this reparameterization was shown to be exactly equivalent to continuous-time mirror descent by Amid and Warmuth 2020, but theory for the analogous discrete time algorithms is left as an open problem. We prove an $O(T^{\frac{2}{3}})$ regret bound for non-convex online gradient descent in this setting, answering this open problem. Our analysis is based on a new and simple algorithmic equivalence method.
△ Less
Submitted 12 October, 2022; v1 submitted 30 May, 2022;
originally announced May 2022.
-
Helicity-conservative Physics-informed Neural Network Model for Navier-Stokes Equations
Authors:
Jiwei Jia,
Young Ju Lee,
Ziqian Li,
Zheng Lu,
Ran Zhang
Abstract:
We design the helicity-conservative physics-informed neural network model for the Navier-Stokes equation in the ideal case. The key is to provide an appropriate PDE model as loss function so that its neural network solutions produce helicity conservation. Physics-informed neural network model is based on the strong form of PDE. We compare the proposed Physics-informed neural network model and a re…
▽ More
We design the helicity-conservative physics-informed neural network model for the Navier-Stokes equation in the ideal case. The key is to provide an appropriate PDE model as loss function so that its neural network solutions produce helicity conservation. Physics-informed neural network model is based on the strong form of PDE. We compare the proposed Physics-informed neural network model and a relevant helicity-conservative finite element method. We arrive at the conclusion that the strong form PDE is better suited for conservation issues. We also present theoretical justifications for helicity conservation as well as supporting numerical calculations.
△ Less
Submitted 3 April, 2024; v1 submitted 15 April, 2022;
originally announced April 2022.
-
On basic $2$-arc-transitive graphs
Authors:
Zai Ping Lu,
Ruo Yu Song
Abstract:
A connected graph $Γ=(V,E)$ of valency at least $3$ is called a basic $2$-arc-transitive graph if its full automorphism group has a subgroup $G$ with the following properties: (i) $G$ acts transitively on the set of $2$-arcs of $Γ$, and (ii) every minimal normal subgroup of $G$ has at most two orbits on $V$.
In her papers [17,18], Praeger proved a connected $2$-arc-transitive graph of valency at…
▽ More
A connected graph $Γ=(V,E)$ of valency at least $3$ is called a basic $2$-arc-transitive graph if its full automorphism group has a subgroup $G$ with the following properties: (i) $G$ acts transitively on the set of $2$-arcs of $Γ$, and (ii) every minimal normal subgroup of $G$ has at most two orbits on $V$.
In her papers [17,18], Praeger proved a connected $2$-arc-transitive graph of valency at least $3$ is a normal cover of some basic $2$-arc-transitive graph, and characterized the group-theoretic structures for basic $2$-arc-transitive graphs.
Based on Praeger's theorems on $2$-arc-transitive graphs, this paper presents a further understanding on basic $2$-arc-transitive graphs.
△ Less
Submitted 9 October, 2022; v1 submitted 15 April, 2022;
originally announced April 2022.
-
Adaptive Gradient Methods with Local Guarantees
Authors:
Zhou Lu,
Wenhan Xia,
Sanjeev Arora,
Elad Hazan
Abstract:
Adaptive gradient methods are the method of choice for optimization in machine learning and used to train the largest deep models. In this paper we study the problem of learning a local preconditioner, that can change as the data is changing along the optimization trajectory. We propose an adaptive gradient method that has provable adaptive regret guarantees vs. the best local preconditioner. To d…
▽ More
Adaptive gradient methods are the method of choice for optimization in machine learning and used to train the largest deep models. In this paper we study the problem of learning a local preconditioner, that can change as the data is changing along the optimization trajectory. We propose an adaptive gradient method that has provable adaptive regret guarantees vs. the best local preconditioner. To derive this guarantee, we prove a new adaptive regret bound in online learning that improves upon previous adaptive online learning methods. We demonstrate the robustness of our method in automatically choosing the optimal learning rate schedule for popular benchmarking tasks in vision and language domains. Without the need to manually tune a learning rate schedule, our method can, in a single run, achieve comparable and stable task accuracy as a fine-tuned optimizer.
△ Less
Submitted 25 January, 2023; v1 submitted 2 March, 2022;
originally announced March 2022.
-
Delta family approach for the stochastic control problems of utility maximization
Authors:
Jingtang Ma,
Zhengyang Lu,
Zhenyu Cui
Abstract:
In this paper, we propose a new approach for stochastic control problems arising from utility maximization. The main idea is to directly start from the dynamical programming equation and compute the conditional expectation using a novel representation of the conditional density function through the Dirac Delta function and the corresponding series representation. We obtain an explicit series repre…
▽ More
In this paper, we propose a new approach for stochastic control problems arising from utility maximization. The main idea is to directly start from the dynamical programming equation and compute the conditional expectation using a novel representation of the conditional density function through the Dirac Delta function and the corresponding series representation. We obtain an explicit series representation of the value function, whose coefficients are expressed through integration of the value function at a later time point against a chosen basis function. Thus we are able to set up a recursive integration time-stepping scheme to compute the optimal value function given the known terminal condition, e.g. utility function. Due to tensor decomposition property of the Dirac Delta function in high dimensions, it is straightforward to extend our approach to solving high-dimensional stochastic control problems. The backward recursive nature of the method also allows for solving stochastic control and stopping problems, i.e. mixed control problems. We illustrate the method through solving some two-dimensional stochastic control (and stopping) problems, including the case under the classical and rough Heston stochastic volatility models, and stochastic local volatility models such as the stochastic alpha beta rho (SABR) model.
△ Less
Submitted 25 February, 2022;
originally announced February 2022.
-
A piecewise deterministic Markov process approach modeling a dry friction problem with noise
Authors:
Josselin Garnier,
Ziyu Lu,
Laurent Mertz
Abstract:
Understanding and predicting the dynamical properties of systems involving dry friction is a major concern in physics and engineering. It abounds in many mechanical processes, from the sound produced by a violin to the screeching of chalk on a blackboard to human infant crawling dynamics and friction-based locomotion of a multitude of living organisms (snakes, bacteria, scallops..) to the displace…
▽ More
Understanding and predicting the dynamical properties of systems involving dry friction is a major concern in physics and engineering. It abounds in many mechanical processes, from the sound produced by a violin to the screeching of chalk on a blackboard to human infant crawling dynamics and friction-based locomotion of a multitude of living organisms (snakes, bacteria, scallops..) to the displacement of mechanical structures (building, bridges, nuclear plants, massive industrial infrastructures) under earthquakes and beyond. Surprisingly, even for low-dimensional systems, the modeling of dry friction in the presence of random forcing has not been elucidated. In this paper, we propose a piecewise deterministic Markov process approach modeling a system with dry friction including different coefficients for the static and dynamic forces. In this mathematical framework, we derive the corresponding Kolmogorov equations and related tools to compute statistical quantities of interest related to the distributions of the static (sticked) and dynamic phases. We show ergodicity and provide a representation formula of the stationary measure using independent identically distributed portions of the trajectory (excursions). We also obtain deterministic characterizations of the Laplace transforms of the probability density functions of the durations of the static and dynamic phases.
△ Less
Submitted 15 May, 2023; v1 submitted 25 February, 2022;
originally announced February 2022.
-
Equivariant Bordism of 2-Torus Manifolds and Unitary Toric Manifolds
Authors:
Bo Chen,
Zhi Lü,
Qiangbo Tan
Abstract:
The equivariant bordism classification of manifolds with group actions is an essential subject in the study of transformation groups. We are interesting in the action of 2-torus group $\mathbb{Z}_2^n$ and torus group $T^n$, and study the equivariant bordism of 2-torus manifolds and unitary toric manifolds. In this paper, we give a new description of the group $\mathcal{Z}_n(\mathbb{Z}_2^n)$ of 2-t…
▽ More
The equivariant bordism classification of manifolds with group actions is an essential subject in the study of transformation groups. We are interesting in the action of 2-torus group $\mathbb{Z}_2^n$ and torus group $T^n$, and study the equivariant bordism of 2-torus manifolds and unitary toric manifolds. In this paper, we give a new description of the group $\mathcal{Z}_n(\mathbb{Z}_2^n)$ of 2-torus manifolds, and determine the dimention of $\mathcal{Z}_n(\mathbb{Z}_2^n)$ as a $\mathbb{Z}_2$-vector space. With the help of toric topology, Lü and Tan proved that the bordism groups $\mathcal{Z}_n(\mathbb{Z}_2^n)$ are generated by small covers. We will give a new proof to this result. These results can be generalized to the equivariant bordism of unitary toric manifolds, that is, we will give a new description of the group $\mathcal{Z}_n^U(T^n)$ of unitary torus manifolds, and prove that $\mathcal{Z}_n^U(T^n)$ can be generated by quasitoric manifolds with omniorientations.
△ Less
Submitted 22 February, 2022;
originally announced February 2022.
-
Penalty and Augmented Lagrangian Methods for Constrained DC Programming
Authors:
Zhaosong Lu,
Zhe Sun,
Zirui Zhou
Abstract:
In this paper we consider a class of structured nonsmooth difference-of-convex (DC) constrained DC program in which the first convex component of the objective and constraints is the sum of a smooth and nonsmooth functions while their second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have a weak convergence guarantee or…
▽ More
In this paper we consider a class of structured nonsmooth difference-of-convex (DC) constrained DC program in which the first convex component of the objective and constraints is the sum of a smooth and nonsmooth functions while their second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have a weak convergence guarantee or require a feasible initial point. Inspired by the recent work (Math Oper. Res. 42(1):95--118, 2017 by Pang et al.), in this paper we propose two infeasible methods with strong convergence guarantee for the considered problem. The first one is a penalty method that consists of finding an approximate D-stationary point of a sequence of penalty subproblems. We show that any feasible accumulation point of the solution sequence generated by such a penalty method is a B-stationary point of the problem under a weakest possible assumption that it satisfies a pointwise Slater constraint qualification (PSCQ). The second one is an augmented Lagrangian (AL) method that consists of finding an approximate D-stationary point of a sequence of AL subproblems. Under the same PSCQ condition as for the penalty method, we show that any feasible accumulation point of the solution sequence generated by such an AL method is a B-stationary point of the problem, and moreover, it satisfies a KKT type of optimality condition for the problem, together with any accumulation point of the sequence of a set of auxiliary Lagrangian multipliers. We also propose an efficient successive convex approximation method for computing an approximate D-stationary point of the penalty and AL subproblems. Finally, some numerical experiments are conducted to demonstrate the efficiency of our proposed methods.
△ Less
Submitted 17 November, 2021;
originally announced November 2021.
