Search for: All records

Creators/Authors contains: "Lyu, Hanbaek"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. We study model-free policy optimization algorithms for regret minimization in infinite horizon average reward Markov decision processes. Optimal regret bounds in this setting are only available under the restrictive uniform mixing assumption which states that, regardless of the policy one uses, the underlying Markov chain converges to its stationary behavior at a constant exponential rate. In this paper, we challenge this strong assumption and present the first provably efficient policy optimization method for infinite horizon average reward Markov decision processes without any mixing time dependence. Our algorithm achieves the optimal O~(sqrt(T)) regret assuming only a data coverage condition and the existence of a recurrent state that is re-visited within a finite expected time under all policies. Our results are obtained through a novel randomized episode length which allows us to leverage the Markov chain's renewal property. 
    more » « less
    Free, publicly-accessible full text available August 15, 2027
  2. Free, publicly-accessible full text available July 1, 2027
  3. Free, publicly-accessible full text available February 2, 2027
  4. Block majorization-minimization (BMM) is a simple iterative algorithm for nonconvex optimization that sequentially minimizes a majorizing surrogate of the objective function in each block coordinate while the other block coordinates are held fixed. We consider a family of BMM algorithms for minimizing nonsmooth nonconvex objectives, where each parameter block is constrained within a subset of a Riemannian manifold. We establish that this algorithm converges asymptotically to the set of stationary points, and attains an epsilon-stationary point within O(epsilon^-2) iterations. In particular, the assumptions for our complexity results are completely Euclidean when the underlying manifold is a product of Euclidean or Stiefel manifolds, although our analysis makes explicit use of the Riemannian geometry. Our general analysis applies to a wide range of algorithms with Riemannian constraints: Riemannian MM, block projected gradient descent, Bures-JKO scheme for Wasserstein variational inference, optimistic likelihood estimation, geodesically constrained subspace tracking, robust PCA, and Riemannian CP-dictionary-learning. We experimentally validate that our algorithm converges faster than standard Euclidean algorithms applied to the Riemannian setting. 
    more » « less
    Free, publicly-accessible full text available February 2, 2027
  5. Free, publicly-accessible full text available December 2, 2026
  6. Berkenkamp, Felix; Fazel, Maryam; Hsu, Daniel; Lacoste-Julien, Simon; Singh, Aarti; Maharaj, Tegan; Zhu, Jerry (Ed.)
  7. Free, publicly-accessible full text available January 1, 2027
  8. Berkenkamp, Felix; Fazel, Maryam; Hsu, Daniel; Lacoste-Julien, Simon; Maharaj, Tegan; Singh, Aarti; Wagstaff, Kiri; Zhu, Jerry (Ed.)
    We consider the branch-length estimation problem on a bifurcating tree: a character evolves along the edges of a binary tree according to a two-state symmetric Markov process, and we seek to recover the edge transition probabilities from repeated observations at the leaves. This problem arises in phylogenetics, and is related to latent tree graphical model inference. In general, the log-likelihood function is non-concave and may admit many critical points. Nevertheless, simple coordinate maximization has been known to perform well in practice, defying the complexity of the likelihood landscape. In this work, we provide the first theoretical guarantee as to why this might be the case. We show that deep inside the Kesten-Stigum reconstruction regime, provided with polynomially many m samples (assuming the tree is balanced), there exists a universal parameter regime (independent of the size of the tree) where the log-likelihood function is strongly concave and smooth with high probability. On this high-probability likelihood landscape event, we show that the standard coordinate maximization algorithm converges exponentially fast to the maximum likelihood estimator, which is within O(1/sqrt(m)) from the true parameter, provided a sufficiently close initial point. 
    more » « less
  9. The classical static Schrödinger Bridge (SSB) problem, which seeks the most likely stochastic evolution between two marginal probability measures, has been studied extensively in the optimal transport and statistical physics communities, and more recently in machine learning communities in the surge of generative models. The standard approach to solve SSB is to first identify its Kantorovich dual and use Sinkhorn's algorithm to find the optimal potential functions. While the original SSB is only a strictly convex minimization problem, this approach is known to warrant linear convergence under mild assumptions. In this work, we consider a generalized SSB allowing any strictly increasing divergence functional, far generalizing the entropy functional x log(x) in the standard SSB. This problem naturally arises in a wide range of seemingly unrelated problems in entropic optimal transport, random graphs/matrices, and combinatorics. We establish Kantorovich duality and linear convergence of Sinkhorn's algorithm for the generalized SSB problem under mild conditions. Our results provide a new rigorous foundation for understanding Sinkhorn-type iterative methods in the context of large-scale generalized Schrödinger bridges. 
    more » « less
  10. Block majorization-minimization (BMM) is a simple iterative algorithm for constrained nonconvex optimization that sequentially minimizes majorizing surrogates of the objective function in each block while the others are held fixed. BMM entails a large class of optimization algorithms such as block coordinate descent and its proximal-point variant, expectation-minimization, and block projected gradient descent. We first establish that for general constrained nonsmooth nonconvex optimization, BMM with rho-strongly convex and L_g-smooth surrogates can produce an epsilon-approximate first-order optimal point within O~((1+L_g+rho^-1) epsilon^-2) iterations and asymptotically converges to the set of first-order optimal points. Next, we show that BMM combined with trust-region methods with diminishing radius has an improved complexity of O~((1+L_g) epsilon^-2), independent of the inverse strong convexity parameter rho^-1, allowing improved theoretical and practical performance with "flat" surrogates. Our results hold robustly even when the convex subproblems are solved inexactly as long as the optimality gaps are summable. Central to our analysis is a novel continuous first-order optimality measure, by which we bound the worst-case suboptimality in each iteration by the first-order improvement the algorithm makes. We apply our general framework to obtain new results on various algorithms such as the celebrated multiplicative update algorithm for nonnegative matrix factorization by Lee and Seung, regularized nonnegative tensor decomposition, and the classical block projected gradient descent algorithm. Lastly, we numerically demonstrate that the additional use of diminishing radius can improve the convergence rate of BMM in many instances. 
    more » « less