Publication

Composite Self-Concordant Minimization

Related publications (15)

Social Learning with Disparate Hypotheses

Ali H. Sayed, Stefan Vlaski, Virginia Bordignon, Konstantinos Ntemos

In this paper we study the problem of social learning under multiple true hypotheses and self-interested agents. In this setup, each agent receives data that might be generated from a different hypothesis (or state) than the data other agents receive. In c ...

IEEE2022

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

Nicolas Boumal, Christopher Arnold Criscitiello

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical ...

SPRINGER2022

A first-order primal-dual method with adaptivity to local smoothness

Volkan Cevher, Maria-Luiza Vladarean

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

2021

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

A Newton Frank-Wolfe method for constrained self-concordant minimization

Volkan Cevher, Quoc Tran Dinh

We develop a new Newton Frank-Wolfe algorithm to solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO). Unlike L-smooth convex functions, where the Lipschitz continuity of the objective gradient holds gl ...

SPRINGER2022

Data-Driven Chance Constrained Programs over Wasserstein Balls

Daniel Kuhn, Wolfram Wiesemann, Zhi Chen

We provide an exact deterministic reformulation for data-driven chance constrained programs over Wasserstein balls. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, our reformulation amounts to a mixed ...

2024

A Non-Euclidean Gradient Descent Framework for Non-Convex Matrix Factorization

Volkan Cevher, Anastasios Kyrillidis, Rabeeh Karimi Mahabadi, Ya-Ping Hsieh, Yu-Chun Kao

We study convex optimization problems that feature low-rank matrix solutions. In such scenarios, non-convex methods offer significant advantages over convex methods due to their lower space complexity as well as faster convergence speed. Moreover, many of ...

2018

Composite convex minimization involving self-concordant-like cost functions

Volkan Cevher, Yen-Huan Li, Quoc Tran Dinh

The self-concordant-like property of a smooth convex func- tion is a new analytical structure that generalizes the self-concordant notion. While a wide variety of important applications feature the self- concordant-like property, this concept has heretofor ...

2015

Composite convex minimization involving self-concordant-like cost functions

Volkan Cevher, Yen-Huan Li, Quoc Tran Dinh

The self-concordant-like property of a smooth convex function is a new analytical structure that generalizes the self-concordant notion. While a wide variety of important applications feature the self- concordant-like property, this concept has heretofore ...

2015

Path-following gradient-based decomposition algorithms for separable convex optimization

Quoc Tran Dinh

A new decomposition optimization algorithm, called path-following gradient-based decomposition, is proposed to solve separable convex optimization problems. Unlike path-following Newton methods considered in the literature, this algorithm does not require ...

Springer Verlag2014

Barrier Smoothing for Nonsmooth Convex Minimization

Volkan Cevher, Yen-Huan Li, Quoc Tran Dinh

This paper proposes a smoothing technique for nonsmooth convex minimization using self-concordant barriers. To illustrate the main ideas, we compare our technique and the proximity smoothing approach (Nesterov2005) via the classical gradient method on both ...

Ieee2014

Fast Proximal algorithms for Self-concordant function minimization with application to sparse graph selection

Volkan Cevher, Anastasios Kyrillidis

The convex

\ell_1

-regularized

\log\det

divergence criterion has been shown to produce theoretically consistent graph learning. However, this objective function is challenging since the

\ell_1

-regularization is nonsmooth, the

\log\det

objective is n ...

2013

Fast Proximal Algorithms For Self-Concordant Function Minimization With Application To Sparse Graph Selection

Volkan Cevher, Anastasios Kyrillidis

The convex l(1)-regularized log det divergence criterion has been shown to produce theoretically consistent graph learning. However, this objective function is challenging since the l(1)-regularization is nonsmooth, the log det objective is not globally Li ...

IEEE2013

A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions

Volkan Cevher, Anastasios Kyrillidis, Quoc Tran Dinh

We propose an algorithmic framework for convex minimization problems of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term. Our method is a new proximal Newton algorithm that features a local quadra ...

2013

Geometry-aware analysis of high-dimensional visual information sets

Effrosyni Kokiopoulou

Over the past few decades we have been experiencing a data explosion; massive amounts of data are increasingly collected and multimedia databases, such as YouTube and Flickr, are rapidly expanding. At the same time rapid technological advancements in mobil ...

EPFL2009