The stochastic gradient (SG) method can quickly solve a problem with a large number of components in the objective, or a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, can quickly solve problems with multiple (blocks of) variables. This paper introduces a method that combines the great features of SG and BCD for problems with many components in the objective and with multiple (blocks of) variables. This paper proposes a block SG (BSG) method for both convex and nonconvex programs. BSG generalizes SG by updating all the blocks of variables in the Gauss–Seidel type (updating the current block depends on the previously updated block), in either a fixed or randomly shuffled order. Although BSG has slightly more work at each iteration, it typically outperforms SG because of BSG’s Gauss–Seidel updates and larger step sizes, the latter of which are determined by the smaller per-block Lipschitz constants. The convergence of BSG is established for both convex and nonconvex cases. In the convex case, BSG has the same order of convergence rate as SG. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. In both cases our analysis is nontrivial since the typical unbiasedness assumption no longer holds. BSG is numerically evaluated on the following problems: stochastic least squares and logistic regression, which are convex, and low-rank tensor recovery and bilinear logistic regression, which are nonconvex. On the convex problems, BSG performed significantly better than SG. On the nonconvex problems, BSG significantly outperformed the deterministic BCD method because the latter tends to stagnate early near local minimizers. Overall, BSG inherits the benefits of both SG approximation and block coordinate updates and is especially useful for solving large-scale nonconvex problems.

In this note we establish some general finiteness results concerning lattices Γ in connected Lie groups$G$which possess certain “density” properties (see$Moskowitz$, M., On the density theorems of Borel and Furstenberg,$Ark. Mat.$$16$(1978), 11–27, and$Moskowitz$, M., Some results on automorphisms of bounded displacement and bounded cocycles,$Monatsh. Math.$$85$(1978), 323–336). For such groups we show that Γ always has finite index in its normalizer$N$_{$G$}(Γ). We then investigate analogous questions for the automorphism group Aut($G$) proving, under appropriate conditions, that Stab_{Aut($G$)}(Γ) is discrete. Finally we show, under appropriate conditions, that the subgroup $\tilde{\Gamma}=\{i_{\gamma}:\gamma \in \Gamma \},\ i_{\gamma}(x)=\gamma x\gamma^{-1}$ , of Aut($G$) has finite index in Stab_{Aut($G$)}(Γ). We test the limits of our results with various examples and counterexamples.

We consider left-invariant distances d on a Lie group G with the property that there exists a multiplicative one-parameter group of Lie automorphisms (0,∞)→Aut(G), λ↦δλ, so that d(δ_λx,δ_λy)=λd(x,y), for all x,y∈G and all λ>0. First, we show that all such distances are admissible, that is, they induce the manifold topology. Second, we characterize multiplicative one-parameter groups of Lie automorphisms that are dilations for some left-invariant distance in terms of algebraic properties of their infinitesimal generator. Third, we show that an admissible left-invariant distance on a Lie group with at least one nontrivial dilating automorphism is bi-Lipschitz equivalent to one that admits a one-parameter group of dilating automorphisms. Moreover, the infinitesimal generator can be chosen to have spectrum in [1,∞). Fourth, we characterize the automorphisms of a Lie group that are a dilating automorphisms for some admissible distance. Finally, we characterize metric Lie groups admitting a one-parameter group of dilating automorphisms as the only locally compact, isometrically homogeneous metric spaces with metric dilations of all factors. Such metric spaces appear as tangents of doubling metric spaces with unique tangents.

We show that Thurston’s skinning maps of Teichmüller space have finite fibers. The proof centers around a study of two subvarieties of the $${{\rm SL}_2(\mathbb{C})}$$ character variety of a surface—one associated with complex projective structures, and the other associated with a 3-manifold. Using the Morgan–Shalen compactification of the character variety and author’s results on holonomy limits of complex projective structures, we show that these subvarieties have only a discrete set of intersections.

No abstract uploaded!