Michael Friedlander

The dual approach in mathematical optimization refers to a class of techniques for tackling a dual problem that arises from the original problem. Numerous notable improvements in strengthening the dual approach have been promoted in the last two decades because of its superior performance for many large-scale optimization problems. In this thesis, we investigate and extend the dual approach to two classes of optimization problems: structured optimization, whose solutions exhibit specific structures, and federated learning, which aims to collaboratively learn a model from decentralized data sources. In the first part of this thesis, we characterize the dual correspondence in structured optimization. We further show that this dual correspondence allows us to develop efficient algorithms and design new models for structured optimization. In the second part of this thesis, we propose a dual approach to the federated optimization problem. We demonstrate theoretically and empirically that our approach enjoys better convergence guarantees than other primal-based approaches under specific scenarios. We also explore some application scenarios for structured optimization in federated learning. In the third part of this thesis, we study the problem of evaluating clients' contributions in federated learning. We propose fair and efficient contribution valuation metrics for both horizontal and vertical federated learning, where structured optimization plays a crucial role in our design.

View record

First-order methods are gaining substantial interest in the past two decades because of their superior performance in solving today's large-scale problems. In this thesis, we study some widely used first-order methods for problems that satisfy certain structures. Specifically, in the first part, we contribute to coordinate optimization and show that greedy coordinate descent (GCD) has an implicit screening ability that usually selects coordinates that are nonzero at the solution, which explains why GCD works exceptionally well for problems that admit sparse solutions. We also extend the elegant safe-screening rule that depends on duality gap to atomic-norm regularized problems. In the second part, we study online mirror descent (OMD) with unknown time horizon and unbounded domain, which is known to suffer from linear regret. We provide a stabilization technique and show that the stabilized-OMD can achieve sublinear regret. We also build the connection between stabilized-OMD and dual averaging. In the third part, we derive improved iteration complexity of the stochastic subgradient method for over-parameterized models that satisfy an interpolation condition. The obtained iteration complexity matches the rate of the stochastic gradient method applied to smooth problems that also satisfy an interpolation condition. Our analysis partially explains the empirical observation that nonsmoothness in modern machine learning models sometimes does not slow down the training process.

View record

The emergence of compressed sensing and its impact on various applications in signal processing and machine learning has sparked an interest in generalizing its concepts and techniques to inverse problems that involve quadratic measurements. Important recent developments borrow ideas from matrix lifting techniques in combinatorial optimization and result in convex optimization problems characterized by solutions with very low rank, and by linear operators that are best treated with matrix-free approaches. Typical applications give rise to enormous optimization problems that challenge even the very best workhorse algorithms and numerical solvers for semidefinite programming.The work presented in this thesis focuses on the class of low-rank spectral optimization problems and its connection with a theoretical duality framework for gauge functions introduced in a seminal paper by Freund (1987). Through this connection, we formulate a related eigenvalue optimization problem more amenable to the design of specialized algorithms that scale well and can be used in practical applications.We begin by exploring the theory of gauge duality focusing on a slightly specialized structure often encountered in the motivating inverse problems. These developments are still made in a rather abstract form, thus allowing for its application to different problem classes.What follows is a connection of this framework with two important classes of spectral optimization problems commonly found in the literature: trace minimization in the cone of positive semidefinite matrices and affine nuclear norm minimization. This leads us to a convex eigenvalue optimization problem with rather simple constraints, and involving a number of variables equal to the number of measurements, thus with dimension far smaller than the primal.The last part of this thesis exploits a sense of strong duality between the primal-dual pair of gauge problems to characterize their solutions and to devise a method for retrieving a primal minimizer from a dual one. This allows us to design and implement a proof of concept solver which compares favorably against solvers designed specifically for the PhaseLift formulation of the celebrated phase recovery problem and a scenario of blind image deconvolution.

View record

The past decade has witnessed the emergence of compressed sensing asa way of acquiring sparsely representable signals in a compressedform. These developments have greatly motivated research in sparsesignal recovery, which lies at the heart of compressed sensing, andwhich has recently found its use in altogether new applications.In the first part of this thesis we study the theoretical aspects ofjoint-sparse recovery by means of sum-of-norms minimization, and theReMBo-l₁ algorithm, which combines boosting techniques withl₁-minimization. For the sum-of-norms approach we derivenecessary and sufficient conditions for recovery, by extendingexisting results to the joint-sparse setting. We focus in particularon minimization of the sum of l₁, and l₂ norms, and giveconcrete examples where recovery succeeds with one formulation butnot with the other. We base our analysis of ReMBo-l₁ on itsgeometrical interpretation, which leads to a study of orthantintersections with randomly oriented subspaces. This workestablishes a clear picture of the mechanics behind the method, andexplains the different aspects of its performance.The second part and main contribution of this thesis is thedevelopment of a framework for solving a wide class of convexoptimization problems for sparse recovery. We provide a detailedaccount of the application of the framework on several problems, butalso consider its limitations. The framework has been implemented inthe SPGL1 algorithm, which is already well established as aneffective solver. Numerical results show that our algorithm isstate-of-the-art, and compares favorably even with solvers for theeasier---but less natural---Lagrangian formulations.The last part of this thesis discusses two supporting softwarepackages: Sparco, which provides a suite of test problems forsparse recovery, and Spot, a Matlab toolbox for the creation andmanipulation of linear operators. Spot greatly facilitates rapidprototyping in sparse recovery and compressed sensing, where linearoperators form the elementary building blocks.Following the practice of reproducible research, all code used forthe experiments and generation of figures is available online athttp://www.cs.ubc.ca/labs/scl/thesis/09vandenBerg/.

View record