Optimization and Control (math.OC)

Abstract: This paper proposes two distributed random reshuffling methods, namely Gradient Tracking with Random Reshuffling (GT-RR) and Exact Diffusion with Random Reshuffling (ED-RR), to solve the distributed optimization problem over a connected network, where a set of agents aim to minimize the average of their local cost functions. Both algorithms invoke random reshuffling (RR) update for each agent, inherit favorable characteristics of RR for minimizing smooth nonconvex objective functions, and improve the performance of previous distributed random reshuffling methods both theoretically and empirically. Specifically, both GT-RR and ED-RR achieve the convergence rate of $O(1/[(1-\lambda)^{1/3}m^{1/3}T^{2/3}])$ in driving the (minimum) expected squared norm of the gradient to zero, where $T$ denotes the number of epochs, $m$ is the sample size for each agent, and $1-\lambda$ represents the spectral gap of the mixing matrix. When the objective functions further satisfy the Polyak-{\L}ojasiewicz (PL) condition, we show GT-RR and ED-RR both achieve $O(1/[(1-\lambda)mT^2])$ convergence rate in terms of the averaged expected differences between the agents' function values and the global minimum value. Notably, both results are comparable to the convergence rates of centralized RR methods (up to constant factors depending on the network topology) and outperform those of previous distributed random reshuffling algorithms. Moreover, we support the theoretical findings with a set of numerical experiments.

Abstract: A novel space-discretized Finite Differences-based model reduction, introduced in (Liu,Guo,2020) is extended to the partial differential equations (PDE) model of a multi-layer Mead-Marcus-type sandwich beam with clamped-free boundary conditions. The PDE model describes transverse vibrations for a sandwich beam whose alternating outer elastic layers constrain viscoelastic core layers, which allow transverse shear. The major goal of this project is to design a single tip velocity sensor to control the overall dynamics on the beam. Since the spectrum of the PDE can not be constructed analytically, the so-called multipliers approach is adopted to prove that the PDE model is exactly observable with sub-optimal observation time. Next, the PDE model is reduced by the ``order-reduced'' Finite-Differences technique. This method does not require any type of filtering though the exact observability as $h\to 0$ is achieved by a constraint on the material constants. The main challenge here is the strong coupling of the shear dynamics of the middle layer with overall bending dynamics. This complicates the absorption of coupling terms in the discrete energy estimates. This is sharply different from a single-layer (Euler-Bernoulli) beam.

Abstract: Stochastic Bilevel optimization usually involves minimizing an upper-level (UL) function that is dependent on the arg-min of a strongly-convex lower-level (LL) function. Several algorithms utilize Neumann series to approximate certain matrix inverses involved in estimating the implicit gradient of the UL function (hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) [16] instead uses stochastic gradient descent steps to solve the linear system associated with the explicit matrix inversion. This modification enables SOBA to match the lower bound of sample complexity for the single-level counterpart in non-convex settings. Unfortunately, the current analysis of SOBA relies on the assumption of higher-order smoothness for the UL and LL functions to achieve optimality. In this paper, we introduce a novel fully single-loop and Hessian-inversion-free algorithmic framework for stochastic bilevel optimization and present a tighter analysis under standard smoothness assumptions (first-order Lipschitzness of the UL function and second-order Lipschitzness of the LL function). Furthermore, we show that by a slight modification of our approach, our algorithm can handle a more general multi-objective robust bilevel optimization problem. For this case, we obtain the state-of-the-art oracle complexity results demonstrating the generality of both the proposed algorithmic and analytic frameworks. Numerical experiments demonstrate the performance gain of the proposed algorithms over existing ones.

Abstract: We study the well-known methods of alternating and simultaneous projections when applied to two nonorthogonal linear subspaces of a real Euclidean space. Assuming that both of the methods have a common starting point chosen from either one of the subspaces, we show that the method of alternating projections converges significantly faster than the method of simultaneous projections. On the other hand, we provide examples of subspaces and starting points, where the method of simultaneous projections outperforms the method of alternating projections.

Abstract: This paper examines the local exponential stability (LES) of trajectories for nonlinear systems on Riemannian manifolds. We present necessary and sufficient conditions for LES of a trajectory on a Riemannian manifold by analyzing the complete lift of the system along the given trajectory. These conditions are coordinate-free which reveal fundamental relationships between exponential stability and incremental stability in a local sense. We then apply these results to design tracking controllers and observers for Euler-Lagrangian systems on manifolds; a notable advantage of our design is that it visibly reveals the effect of curvature on system dynamics and hence suggests compensation terms in the controller and observer. Additionally, we revisit some well-known intrinsic observer problems using our proposed method, which largely simplifies the analysis compared to existing results.